package leetcode.hot100;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _234_回文链表_双指针 {

    // 判断一个链表是否为回文链表
    // 用 O(n) 时间复杂度和 O(1) 空间复杂度解决
    public boolean isPalindrome(ListNode head) {
        // 空链表或只有一个结点也是一种回文链表
        if (head == null || head.next == null) return true;
        // 先找到中心结点，并在此过程中用头插法重新构建一条链表
        ListNode slow = head;
        ListNode fast = head;
        ListNode newHead = null;
        ListNode node;
        while (fast != null && fast.next != null) {
            node = slow;
            fast = fast.next.next;
            slow = slow.next;
            // 头插法
            node.next = newHead;
            newHead = node;
        }
        // 链表长度有可能是奇数，也有可能是偶数
        // 如果fast指针最后指向的是非空，那么就说明链表结点个数是奇数，
        // 这时slow指针刚好指向中间结点，slow指针需要再向下移动一位才能进行回文比较
        // 如果fast指针最后指向的是空，那么链表结点的个数是偶数，这是slow刚好指向另一半链表的起始，不用移动
        if (fast != null) {
            slow = slow.next;
        }
        // 用重新构建的链表和另一半链表进行比较，判断是否回文
        while (newHead != null && slow != null) {
            if (newHead.val != slow.val) return false;
            newHead = newHead.next;
            slow = slow.next;
        }
        return true;
    }
}
